{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 回溯法的作业"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1\n",
    "代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "global ans\n",
    "\n",
    "\n",
    "def task_distribute(n: int, m: int, ret: int, book: set, cost: list) -> None:\n",
    "    \"\"\"\n",
    "    n:总人数/总任务数\n",
    "    m:当前安排到哪个人了（编号从0开始）\n",
    "    ret:目前代价\n",
    "    book:记录已分配的任务数\n",
    "    cost:代价数组\n",
    "    \"\"\"\n",
    "    if m == n:\n",
    "        ans = min(ans, ret)\n",
    "        return\n",
    "    for i in range(n):\n",
    "        if ret >= ans or i in book:\n",
    "            continue\n",
    "        book.add(i)\n",
    "        ret += cost[m][i]\n",
    "        task_distribute(n, 1+m, ret, book, cost)\n",
    "        ret -= cost[m][i]\n",
    "        book.remove(i)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2\n",
    "代码如下："
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15 20 \n",
      "7 10 18 \n",
      "5 12 18 \n",
      "5 10 20 \n"
     ]
    }
   ],
   "source": [
    "global ans, f\n",
    "m = 35\n",
    "w = [5, 7, 10, 12, 15, 18, 20]\n",
    "ans = [0 for i in range(len(w))]\n",
    "f = open(\"images/2.gv\", \"w\")\n",
    "f.write(\"digraph 1 {\\n\")\n",
    "\n",
    "\n",
    "def number_choice(m: int, n: int, ret: int, cnt: int, w: list) -> None:\n",
    "    \"\"\"\n",
    "    m:要求的和\n",
    "    n:目前决策到哪个数了\n",
    "    ret:目前的和\n",
    "    cnt:结点的唯一标识，和画图有关\n",
    "    w:数组\n",
    "    \"\"\"\n",
    "    if n == len(w):  # 决策完毕\n",
    "        # print(ans,end=\" \")\n",
    "        # print(ret)\n",
    "        if ret == m:  # 找到答案\n",
    "            for i in range(len(w)):\n",
    "                if ans[i] != 0:\n",
    "                    print(\"{}\".format(w[i]), end=\" \")\n",
    "            print(\"\")\n",
    "        return\n",
    "    father_node_name = \"node\" + str(cnt)+\"_\" +\\\n",
    "        str(ans).removeprefix(\"[\").removesuffix(\"]\").replace(\", \", \"\")\n",
    "    for i in [0, 1]:\n",
    "        if ret+i*w[n]+sum(w[1+n:]) < m:  # 限界函数\n",
    "            continue\n",
    "        if ret+i*w[n] > m:  # 限界函数\n",
    "            continue\n",
    "        ans[n] = i\n",
    "        cnt += 1\n",
    "        son_node_name = \"node\" + str(cnt) +\"_\" + \\\n",
    "            str(ans).removeprefix(\"[\").removesuffix(\"]\").replace(\", \", \"\")\n",
    "        if father_node_name != son_node_name:\n",
    "            f.write(son_node_name+\";\\n\")\n",
    "            f.write(father_node_name+\"->\"+son_node_name+\";\\n\")\n",
    "        number_choice(m, 1+n, ret+i*w[n], cnt, w)\n",
    "\n",
    "\n",
    "number_choice(m, 0, 0, 0, w)\n",
    "f.write(\"}\")\n",
    "f.close()\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "生成的搜索树如下：   \n",
    "<img src=\"./images/2.svg\" width=100%>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.2"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "a166369db42c1466e2e3775def9041c304cd3bfe227c8b0f35b781bd0a6af835"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
